Logic Workshop

I will begin with an overview of how implicit definition, and variations of Beth's definability theorem, arise in relational databases, particularly in the context of view rewriting.

We then turn from relational databases to nested relational databases, a model of hierarchical data - 'objects' - where tables can contain tuples whose components are again tables. There is a standard transformation language for this data model, the Nested Relational Calculus (NRC). We show that a variant of Gaifman's coordinatization theorem plays a role in lieu of Beth's theorem, allowing one to generate NRC transformations from several kinds of implicit specifications. We discuss how to generate transformations effectively from specifications, which requires the development of proof-theoretic methods for implicit definability over nested sets.

This is joint work with Ceclia Pradic and Christoph Wernhard.

​

It is a well-known empirical phenomenon that natural axiomatic theories are well-ordered by consistency strength. The restriction to natural theories is necessary; using ad-hoc techniques (such as self-reference and Rosser orderings) one can exhibit non-linearity and ill-foundedness in the consistency strength hierarchy. What explains the contrast between natural theories and axiomatic theories in general?

Our approach to this problem is inspired by work on an analogous problem in recursion theory. The natural Turing degrees $(0,0’,\ldots,\text{Kleene’s~}\mathcal{O},\ldots,0^{\#},\ldots)$ are well-ordered by Turing reducibility, yet the Turing degrees in general are neither linearly ordered nor well-founded, as ad-hoc techniques (such as the priority method) bear out. Martin's Conjecture, which is still unresolved, is a proposed explanation for this phenomenon. In particular, Martin’s Conjecture specifies a way in which the Turing jump is canonical.

After discussing Martin’s Conjecture, we will formulate analogous proof-theoretic hypotheses according to which the consistency operator is canonical. We will then discuss results - both positive and negative - within this framework. Some of these results were obtained jointly with Antonio Montalbán.

​

We consider the game of infinite Wordle as played on Baire space $\omega^\omega$. The codebreaker can win in finitely many moves against any countable dictionary $\Delta\subseteq\omega^\omega$, but not against the full dictionary of Baire space. The Wordle number is the size of the smallest dictionary admitting such a winning strategy for the codebreaker, the corresponding Wordle ideal is the ideal generated by these dictionaries, which under MA includes all dictionaries of size less than the continuum. The Absurdle number, meanwhile, is the size of the smallest dictionary admitting a winning strategy for the absurdist in the two-player variant, infinite Absurdle. In ZFC there are nondetermined Absurdle games, with neither player having a winning strategy, but if one drops the axiom of choice, then the principle of Absurdle determinacy has large cardinal consistency strength over ZF+DC. This is joint work with Ben De Bondt (Paris).

​

Galeotti, Khomskii and Väänänen recently introduced the notion of the upward Löwenheim Skolem (ULS) number for an abstract logic. A cardinal $\kappa$ is the upward Lowenheim Skolem number for a logic $\mathcal L$ if it is the least cardinal with the property that whenever $M$ is a model of size at least $\kappa$ satisfying a sentence $\varphi$ in $\mathcal L$, then there are arbitrarily large models $N$ satisfying $\varphi$ and having $M$ as a substructure (not necessarily elementary). If we remove the requirement that $M$ has to be a substructure of $N$, we get the classic notion of a Hanf number. While $\rm ZFC$ proves that every logic has a Hanf number, having a ULS number often turns out to have large cardinal strength. In a joint work with Jonathan Osinski, we study the ULS numbers for several classical logics. We introduce a strengthening of the ULS number, the strong upward Löwenheim Skolem number SULS which strengthens the requirement that $M$ is a substructure to full elementarity in the logic $\mathcal L$. It is easy to see that both the ULS and the SULS number for a logic $\mathcal L$ are bounded by the least strong compactness cardinal for $\mathcal L$, if it exists.

Slides

​

Model-theoretic frameworks for nonstandard methods entail the existence of nonprincipal ultrafilters over $\mathbb N$, a strong version of the Axiom of Choice (AC). While AC is instrumental in many abstract areas of mathematics, such as general topology or functional analysis, its use in infinitesimal calculus or number theory should not be necessary.

Mikhail Katz and I have formulated a set theory SPOT in the language that has, in addition to membership, a unary predicate “is standard.” In addition to ZF, the theory has three simple axioms, Transfer, Nontriviality and Standard Part, that reflect the insights of Leibniz. It is a subtheory of the nonstandard set theories IST and HST, but unlike them, it is a conservative extension of ZF. Arguments carried out in SPOT thus do not depend on any form of AC. Infinitesimal calculus can be developed in SPOT as far as the global version of Peano's Theorem (the usual proofs of which use ADC, the Axiom of Dependent Choice). The existence of upper Banach densities can be proved in SPOT.

The conservativity of SPOT over ZF is established by a construction that combines the methods of forcing developed by Ali Enayat for second-order arithmetic and Mitchell Spector for set theory with large cardinals.

A stronger theory SCOT is a conservative extension of ZF+ADC. It is suitable for handling such features as an infinitesimal approach to the Lebesgue measure.

I will also formulate an extension of SPOT to a theory with multiple levels of standardness SPOTS, in which Renling Jin's recent groundbreaking proof of Szemeredi's Theorem can be carried out. While it is an open question whether SPOTS is conservative over ZF, SPOTS + DC (Dependent Choice for relations definable in it) is a conservative extension of ZF + ADC.

Reference: KH and M. G. Katz, Infinitesimal analysis without the Axiom of Choice, Ann. Pure Applied Logic 172, 6 (2021). https://doi.org/10.1016/j.apal.2021.102959, https://arxiv.org/abs/2009.04980

​

On the basis of Poincaré and Weyl's view of predicativity as invariance, we develop an extensive framework for predicative, type-free first-order set theory in which $\Gamma_0$ and much bigger ordinals can be defined as von Neumann ordinals. This refutes the accepted view of $\Gamma_0$ as the 'limit of predicativity.' We also explain what is wrong in Feferman-Schütte analysis of predicativity on which this view of $\Gamma_0$ is based.

​

Given an $L_{\omega_1\omega}$-sentence $\varphi$ in a countable language, we call an ergodic $S_\infty$-invariant probability measure on the Borel space of countable models of $\varphi$ (having fixed underlying set) an ergodic model of $\varphi$. I will discuss the number of ergodic models of such a sentence $\varphi$, including the case when $\varphi$ is a Scott sentence. This is joint work with N. Ackerman, C. Freer, A. Kruckman and A. Kwiatkowska.

​

In 1982 Makkai published a very general theorem about the existence of what he later called principally prime (we call them positive atomic) models of so-called regular theories [FULL CONTINUOUS EMBEDDINGS OF TOPOSES, TAMS 269], which seems to have gone largely unnoticed. (Regular he called those theories that are axiomatized by positive primitive (=pp) implications.) This is a strong existence result in some sort of positive logic in a very general categorical (including non-additive) setting. I first discuss its significance for definable subcategories of modules (=model categories of regular theories of modules), which play an important role in representation theory and module theory in general. Part of this is that there these models are precisely the strict Mittag-Leffler modules contained in and relativized to such definable subcategories. Makkai’s original proof is, in its generality, not easy to follow, and so it is of interest, especially to the algebraic community, to find an easier proof for modules. I present a recent one due to Prest. At the time being it works only for countable rings, in the uncountable case one still has to rely on Makkai’s original proof.

​

In the classical pointwise ergodic theorem for a probability measure preserving (pmp) transformation $T$, one takes averages of a given integrable function over the intervals $(x, Tx, T^2 x,...,T^n x)$ in front of the point $x$. We prove a “backward” ergodic theorem for a countable-to-one pmp $T$, where the averages are taken over subtrees of the graph of $T$ that are rooted at $x$ and lie behind $x$ (in the direction of $T^{-1}$). Surprisingly, this theorem yields forward ergodic theorems for countable groups, in particular, one for pmp actions of free groups of finite rank, and can be extended to yield ergodic theorems for pmp actions of free semigroups as well. In each case, the averages are taken along subtrees of the standard Cayley graph rooted at the identity. This is joint work with Anush Tserunyan.

​

We look at differential equations of the form $x^{\prime\prime}/x^\prime=f(x)$ where $f$ is a rational function over the field of constants. We characterize when such equations are strongly minimal and study algebraic relations between solutions to two such equations.

​

A more correct title would read: the model-theory of the category of compact (Hausdorff) spaces. Last year, I gave a talk about the model-theory of categories, and this talk will be its continuation (but I will repeat everything that is relevant) in which I will look at one special case: COMP, the category of compact spaces. Let C be any model that is elementary equivalent to the category COMP (but if you’re a standard guy, you can just take C=COMP and everything is still interesting). The model C 'remembers' the topology of each of its objects (except we might have lost compactness). But it can recover much more, to an extent that I would almost call it 'foundational'. I will show how to reconstruct a model of PA, a model of the ORD (ordinals) and even a model of ZFC. If you wonder, which model of ZFC you get if you just start with COMP, the answer is: the same you woke up to this morning!

​